package cn.hesion.leetcode;
/**
 * ClassName: FindNthDigit <br/>
 * Description: <br/>
 * date: 2022/6/9 7:22<br/>
 *
 * @author Hesion<br />
 * @version
 * @since JDK 1.8
 */

import java.util.Collection;
import java.util.Collections;
import java.util.Stack;

/**
 * 400. 第 N 位数字
 *
 * @author: hesion
 * @create: 2022-06-09 07:22
 **/
public class FindNthDigit {
    public int findNthDigit(int n) {
        long ln = n, nine = 9;

        int i;
        for (i = 1; i <= 15; ++i) {
            ln -= nine * i;
            if (ln <= 0) {
                ln += nine * i;
                break;
            }
            nine *= 10;
        }

        long l = nine / 9;
        long r = l * 10 - 1;
        long ans = -1;
        while (l <= r) {
            long mid = (l + r) >> 1;
            long cnt = (mid - nine / 9 + 1) * i;
            if (cnt >= ln) {
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        Stack<Long> stack = new Stack<Long>();
        while (ans >= 1) {
            stack.push(ans % 10);
            ans /= 10;
        }
        Collections.reverse(stack);
        System.out.println(stack);
        Long aLong= 0L;
        if (stack.size() != 0) {
            aLong = stack.get((int) ((ln - 1) % i));
        }
        return aLong.intValue();
    }

    public static void main(String[] args) {
        new FindNthDigit().findNthDigit(10);
    }

}
